This invention relates in general to digital decoding and more specifically to a decoding system especially suited for MPEG-type decoding.
The Moving Pictures Experts Group (MPEG) standards of compression have gained wide popularity. The MPEG standards are used extensively in digital audio and image compression, encoding, transfer and decoding and decompression. Copies of the standards are available from many sources. On such source is the MPEG home page at http://www.cselt.it/mpeg/.
Implementing the MPEG standard in a computer, server, consumer electronic device, or other digital system can be daunting because of the enormous bandwidth and throughput requirements of today""s MPEG content. Devices that play back MPEG content must be very fast. Often such devices are restricted to very limited resources. Thus, any improvements in efficiency in implementing various aspects of the MPEG standard are welcome and valuable.
One MPEG standard function that can greatly benefit from improvement is MPEG decoding. MPEG decoding occurs at the time of playback of MPEG content. This often means that the decoder is executing in a consumer electronic device with very limited resources. For example, such consumer electronics devices often have simple, slower processors that are also used for other tasks in the device. The amount of memory, or other storage, is limited and is needed by other tasks or features in the device.
A significant portion of MPEG decoding involves decoding bitstreams that represent audio or image content (or both). A bitstream includes variable length coding (VLC) code words. Each code word is a variable number of bits. One use of VLC code words is to decode discrete cosine transform coefficients. In this case, each code word indicates (1) the number of zeros before the next coefficient (the xe2x80x9crunxe2x80x9d), (2) the value of the next coefficient (the xe2x80x9clevelxe2x80x9d) and (3) how to obtain the next code word in the bitstream (i.e., the xe2x80x9clengthxe2x80x9d of the present code word).
Table I, below, shows selected VLC code words used to decode DCT coefficients. A complete set of VLC code words can be found in the MPEG standards. In Table I, xe2x80x9crunxe2x80x9d indicates the number of zeros until the next non-zero coefficient and xe2x80x9clevelxe2x80x9d is the value of the coefficient. There are 114 code words for this particular example.
Run-level pairs that occur more frequently are assigned short code words while those occurring less frequently are assigned long code words, effectively compressing the data since the more frequent shorter code words dominate. Only the codes with high probability of occurrence are coded with a VLC. Less probable events are coded with an escape symbol followed by fixed length codes.
The basic idea of VLC decoding is to match bit patterns of an incoming bitstream against a codebook containing all of the allowed bit patterns. A simple decoding algorithm would check the bitstream one bit at a time until a matching pattern was found. For most applications, such an approach is far too slow to be practical; and, commonly, decoding speed is increased by matching multiple bits at a time using lookup tables.
Programmable processors are frequently employed for VLC decoding, but they are relatively inefficient because of their fixed word sizes as well as their modest shifting and bit testing capabilities.
Many approaches exist for decoding VLC encoded coefficients. See, e.g., xe2x80x9cMPEG-2 Video Decoding on the TMS320C6X DSP Architecture,xe2x80x9d Sundararajan Sriram, and Ching-Yu Hung.
The present invention provides a fast, memory efficient, lookup table-based system for VLC decoding. Code words are grouped by prefix and recoded to reduce the number of bits that must be matched, reducing the memory requirements. General-purpose processor and finite state machine (FSM) decoder implementations are described.